package sort;

import java.util.*;

public class LinearSorts {
    public static void main(String[] args) {
        int[] a = new int[]{9, 0, 34, 223, -232, -7, 99, -87, 230, 5, 88, 3, 1, 22, 300, -43, -232, -7, 1, 4, 5, 6};
        System.out.println(Arrays.toString(a));
        bucketSort(a);
        System.out.println(Arrays.toString(a));
    }

    private static void radixSort(int[] a) {
        if (a.length == 1) return;
        Queue<Integer>[] buckets = new ArrayDeque[10];
        for (int i = 0; i < 10; i++) buckets[i] = new ArrayDeque<Integer>();
        int divisor = 1;
        do {
            for (int number : a) {
                int digit = (Math.abs(number) / divisor) % 10;
                buckets[digit].add(number);
            }
            divisor *= 10;
            if (buckets[0].size() == a.length) {// We reached the end, the most significant digit
                Deque<Integer> negativeBucket = new ArrayDeque<Integer>();
                final Iterator<Integer> iterator = buckets[0].iterator();
                while (iterator.hasNext()) {
                    int number = iterator.next();
                    if (number < 0) {
                        negativeBucket.add(number);
                        iterator.remove();
                    }
                }
                if (negativeBucket.isEmpty()) return; // The input array contains no negative values
                int index = 0;
                while (!negativeBucket.isEmpty()) a[index++] = negativeBucket.removeLast();
                while (!buckets[0].isEmpty()) a[index++] = buckets[0].remove();
                return;
            }
            for (int i = 0, j = 0; i < 10; i++) while (!buckets[i].isEmpty()) a[j++] = buckets[i].remove();
        } while (true);
    }

    private static void countingSort(int[] a) {
        if (a == null || a.length == 1) return;
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
            if (a[i] > max) max = a[i];
        }

        int[] counts = new int[max - min + 1];
        for (int i = 0; i < a.length; i++) counts[a[i] - min]++;
        for (int i = 0, j = 0; i < counts.length; i++) {
            for (int k = counts[i]; k > 0; k--) {
                a[j++] = i + min;
            }
        }
    }

    private static void bucketSort(int[] a) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            if (a[i] < min) min = a[i];
            if (a[i] > max) max = a[i];
        }
        Deque<Integer>[] buckets = new Deque[a.length];
        for (int i = 0; i < a.length; i++) buckets[i] = new ArrayDeque<Integer>();
        for (int i = 0; i < a.length; i++) buckets[indexOf(a[i], min, max, a.length)].add(a[i]);
        for (int i = 0; i < a.length; i++) sortTheBucket(buckets[i]);

        int index = 0;
        for (int i = 0; i < a.length; i++) while (!buckets[i].isEmpty()) a[index++] = buckets[i].remove();
    }

    private static void sortTheBucket(Deque<Integer> bucket) {
        if (bucket.size() <= 1) return;
        final Integer[] a = new Integer[bucket.size()];
        bucket.toArray(a);
        /*for (int i = 1; i < a.length; i++) {
            int temp = a[i];
            int j = i - 1;
            while (j >= 0 && a[j] > temp) {
                a[j + 1] = a[j];
                j--;
            }
            a[j + 1] = temp;
        }*/

        for (int i = 1; i < a.length; i++)
            for (int j = i - 1; j > 0 && (a[j-1] > a[j]); j--) swap(a, j-1, j);
        bucket.clear();
        for (Integer number : a) bucket.add(number);

    }

    private static void swap(Integer[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    private static int indexOf(int element, int min, int max, int length) {
        if (element == min) return 0;
        if (element == max) return length - 1;
        return (int) (1.0 * (element - min) / (max - min) * length);
    }

}
